package com.gxc.sort;

import java.util.Stack;

/**
 * 请编写一个程序，对一个栈里的整型数据，按升序进行排序(即排序前，栈里的数据是无序的，排序后最大元素位于栈顶)，
 * 要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中
 */
public class StackSort {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            int[] array = randomArray();
            Stack<Integer> a = random(array);
            Stack<Integer> b = random(array);

            extraOne(a);
            process(b);

            while (!a.isEmpty()) {
                if (a.pop()!=b.pop()) {
                    System.out.println("算法错误");
                    break;
                }
            }
        }

        int[] c = new int[]{39  ,  71   , 15   , 97   , 65    ,24};
        Stack<Integer> a = random(c);
        Stack<Integer> b = random(c);
        extraOne(a);
        process(b);
        while (!b.isEmpty()) {
            System.out.print(b.pop() + " ");
        }
        System.out.println("-------------");
    }

    /**
     * 1.从原始栈中经过比较把最大的值压入额外栈内
     * @param stack
     */
    private static void extraOne(Stack<Integer> stack) {
        if (stack.isEmpty()) return;
        Stack<Integer> extra = new Stack<>();

        int size =stack.size();
        for (int i = 0; i < size; i++) {
            int max = Integer.MIN_VALUE;
            while (!stack.isEmpty()) {
                Integer pop = stack.pop();
                if (pop > max) {
                    if (max!=Integer.MIN_VALUE) extra.push(max);
                    max = pop;
                }
                else extra.push(pop);
            }
            while (extra.size()>i) {
                stack.push(extra.pop());
            }
            extra.push(max);
        }

        while (!extra.isEmpty()) {
            stack.push(extra.pop());
        }
    }

    private static void process(Stack<Integer> stack) {
        if (stack.isEmpty()) return;
        Stack<Integer> help = new Stack<>();

        while (!stack.isEmpty()) {
            Integer top = stack.pop();
            //辅助栈顶的元素小于当前，则辅助栈顶，压入初始栈，保持辅助栈是从底向上是从小到大
            while (!help.isEmpty() && help.peek() < top) {
                stack.push(help.pop());
            }
            help.push(top);
        }

        //压回初始栈
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

    private static Stack<Integer> random(int[] array) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < array.length; i++) {
            stack.push(array[i]);
        }
        return stack;
    }

    private static int[] randomArray() {
        int size = (int) (100 * Math.random());
        int[] array = new int[size];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (100 * Math.random());
        }
        return array;
    }

}
